/*
 * array.cpp
 *
 *  Created on: Jul 13, 2012
 *      Author: jh238d
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

/*Rotate a one-dimensional array of n elements to the right by k steps.
For instance, with n=7 and k=3, the array {a, b, c, d, e, f, g} is rotated to {e, f, g, a, b, c, d}*/

void reverse_array(int a[], int left, int right){
	int *p1=a+left;
	int *p2=a+right;
	while(p1<p2){
		int *tmp = p1;
		*p1=*p2;
		*p2=*tmp;
		p1++;
		p2--;
	}
}

void rotate_an_array_in_place(int a[], int n, int k){
	reverse_array(a, 0, n-1);
	reverse_array(a, 0, k-1);
	reverse_array(a, k, n-1);
}

/*There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n).

For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}
 */
void array_multiplication(int a[], int out[], int n){
	int left = 1;
	int right = 1;

	for(int i=0; i<n; i++)
		out[i]=1;

	for(int i=0;i<n;i++){
		out[i]*=left;
		out[n-i-1]*=right;
		left*=a[i];
		right*=a[n-1-i];
	}
}

/* http://www.leetcode.com/2010/05/printing-matrix-in-spiral-order.html
 * Given a matrix (2D array) of m x n elements (m rows, n columns), write a function that prints the elements in the array in a spiral manner.*/

#define N_MAX 1000

void print_matrix_in_spiral_order(int a[][N_MAX], int m, int n, int k){
	if(m<=0||n<=0) return;
	if(m==1){
		for(int i=0;i<n;i++)
			cout<<a[k][k+i]<<" ";
		return;
	}
	if(n==1){
		for(int i=0;i<m;i++)
			cout<<a[k+i][k]<<" ";
		return;
	}
	for(int i=0; i<n-1;i++)
		cout<<a[k][k+i]<<" ";
	for(int i=0; i<m-1;i++)
		cout<<a[k+i][n-1+k]<<" ";
	for(int i=0; i<n-1;i++)
		cout<<a[k+m-1][k+n-1-i]<<" ";
	for(int i=0; i<m-1; i++)
		cout<<a[k+m-1-i][k]<<" ";
	print_matrix_in_spiral_order(a, m-2, n-2, k+1);
}

void print_matrix_in_spiral_order(int a[][N_MAX], int m, int n){
	print_matrix_in_spiral_order(a, m, n, 0);
}
